package leetcode.hash.common;

import leetcode.array.common.ArrayUtils;

import java.util.*;

public class HashUtils {

    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * <p>
     * 2 <= nums.length <= 104
     * -109 <= nums[i] <= 109
     * -109 <= target <= 109
     * 只会存在一个有效答案
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] resultSet = new int[2];
        if (nums == null || nums.length == 0) {
            return resultSet;
        }
        // key--nums[i], value--i
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(target - nums[i]) != null) {
                resultSet[0] = map.get(target - nums[i]);
                resultSet[1] = i;
                return resultSet;
            }
            map.put(nums[i], i);
        }
        return resultSet;
    }

    /**
     * 1 <= nums1.length, nums2.length, nums3.length <= 100
     * 1 <= nums1[i], nums2[j], nums3[k] <= 100
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @return
     */
    public static List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {

        int[] map = new int[105];

        numToMap(nums1, map);
        numToMap(nums2, map);
        numToMap(nums3, map);

        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= 100; i++) {
            if (map[i] >= 2) {
                result.add(i);
            }
        }
        return result;
    }

    private static void numToMap(int[] nums, int[] map) {
        boolean[] showFlag = new boolean[105];
        for (int i = 0; i < nums.length; i++) {
            if (showFlag[nums[i]] == false) {
                map[nums[i]]++;
                showFlag[nums[i]] = true;
            }
        }
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 3) {
            if (Arrays.stream(nums).sum() == 0) {
                result.add(ArrayUtils.intArrayToList(nums));
            }
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            twoSum(nums, i, result);
        }
        return result;
    }

    private static void twoSum(int[] nums, int index, List<List<Integer>> result) {
        int target = -nums[index];
        Map<Integer, Integer> mark = new HashMap<>();
        Integer lastNum = null;
        for (int i = index + 1; i < nums.length; i++) {
            if (lastNum != null && nums[i] == lastNum) {
                continue;
            }
            if (mark.get(target - nums[i]) != null) {
                lastNum = nums[i];
                List<Integer> list = new ArrayList<>();
                list.add(nums[index]);
                list.add(nums[i]);
                list.add(nums[mark.get(target - nums[i])]);
                result.add(list);
            } else {
                mark.put(nums[i], i);
            }
        }
    }

    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            map[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (map[i] != 0) {
                return false;
            }
        }
        return true;
    }

    public static boolean wordPattern(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        Set<String> cacheSet = new HashSet<>();
        int index = 0;
        int point = 0;
        boolean[] show = new boolean[26];
        while (index < pattern.length() && point < s.length()) {
            char c = pattern.charAt(index);
            StringBuilder sub = new StringBuilder();
            while (point < s.length() && s.charAt(point) != ' ') {
                sub.append(s.charAt(point));
                point++;
            }
            if (show[c - 'a']) {
                String s1 = map.get(c);
                if (s1 == null || !s1.equals(sub.toString())) {
                    return false;
                }
            } else {
                show[c - 'a'] = true;
                map.put(c, sub.toString());
                cacheSet.add(sub.toString());
            }
            index++;
            point++;
        }
        return index == pattern.length() && point - 1 == s.length() && cacheSet.size() == map.keySet().size();
    }

    public static int rev(int num) {
        int ans = 0;
        while (num > 0) {
            ans = ans * 10 + num % 10;
            num /= 10;
        }
        return ans;
    }

    public static int countNicePairs(int[] nums) {
        final int MOD = 1000000007; // 即 1e9 + 7
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int revNum = rev(num);
            result = (result + map.getOrDefault(num - revNum, 0)) % MOD;
            map.put(num - revNum, map.getOrDefault(num - revNum, 0) + 1);
        }
        return result;
    }


    public static String decodeMessage(String key, String message) {
        int index = 97;
        Map<Character, Character> map = new HashMap<>();
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (c != ' ' && !map.containsKey(c)) {
                map.put(c, (char) index);
                index++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < message.length(); i++) {
            sb.append(map.getOrDefault(message.charAt(i), ' '));
        }
        return sb.toString();
    }

    public static List<String> alertNames(String[] keyName, String[] keyTime) {
        Map<String, List<Integer>> timeMap = new HashMap<>();
        int n = keyName.length;
        for (int i = 0; i < n; i++) {
            String name = keyName[i];
            String time = keyTime[i];
            timeMap.putIfAbsent(name, new ArrayList<>());
            int hour = (time.charAt(0) - '0') * 10 + (time.charAt(1) - '0');
            int minute = (time.charAt(3) - '0') * 10 + (time.charAt(4) - '0');
            timeMap.get(name).add(hour * 60 + minute);
        }
        List<String> res = new ArrayList<>();
        Set<String> keySet = timeMap.keySet();
        for (String name : keySet) {
            List<Integer> list = timeMap.get(name);
            Collections.sort(list);
            int size = list.size();
            for (int i = 2; i < size; i++) {
                int time1 = list.get(i - 2), time2 = list.get(i);
                int difference = time2 - time1;
                if (difference <= 60) {
                    res.add(name);
                    break;
                }
            }
        }
        Collections.sort(res);
        return res;
    }

    public static int[] numberOfPairs(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            } else {
                set.remove(num);
                count++;
            }
        }
        return new int[]{count, nums.length - 2 * count};
    }
}
